package com.yanyuan.algorithm.sort;

import java.util.Arrays;

/**
 * @Description 快速排序实现
 *  枢轴选取：a.第一个选取法, b.随机数选取法, c.中间值选取法
 * @Author yanyuan
 * @Date 10:31 2020/4/30
 * @Version 1.0
 **/
public class QuickSortDemo {

    /**
     *
     * @param arr 待排数组
     * @param first 起始数组下标
     * @param last  结束数组下标
     */
    public static void sort(int[] arr, int first, int last){
        if(first > last){
            return;
        }
        int pivot = arr[first];//起始枢轴是第一个元素
        int low = first + 1;//low: 从左向右的下标
        int high = last;//high: 从右向左的下标
        while(low <= high){
            //5. 内部循环
            //左 -》 右，找到第一个大于枢轴的元素
            while (low <= last && pivot >= arr[low]){
                low++;
            }
            //右 -》 左，找到第一个小于等于枢轴的元素
            while (first <= high && pivot < arr[high]){
                high--;
            }
            if(low < high){
                int temp = arr[low];
                arr[low] = arr[high];
                arr[high] = temp;
            }
        }
        //first为数组起始位置
        if(first < high){
            int temp = arr[first];
            arr[first] = arr[high];
            arr[high] = temp;
        }
        //继续使用快速排序
        sort(arr, first, high-1);//12. 左侧应用快速排序
        sort(arr, high+1, last);//13.右侧应用快速排序
    }

    public static void main(String[] args) {
        int[] arr = {28, 55, 46, 38, 16, 89, 30};
        sort(arr, 0 , arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
